package airthmetic.exercise.sort.cmp;


import java.util.Random;

// 快速排序
public class _912_排序数组_Quick {

    public int[] sortArray(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }
        quickSort(nums,0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        // terminal
        if (left >= right) {
            return;
        }
        int pivotIndex = partition2(nums,left,right);
        quickSort(nums,left,pivotIndex-1);
        quickSort(nums,pivotIndex+1,right);

    }

    // 第一种快慢指针写法
    public int partition(int[] nums, int left, int right){
        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        swap(nums,pivotIndex,right);
        int pivot = nums[right];
        int i,j;
        i=j=left;
        for (;i<right;i++){
            if (nums[i] <= pivot){
                swap(nums,i,j);
                j++;
            }
        }
        swap(nums,j,right);

        return j;

    }


    // 第二种双指针夹逼写法
    public int partition2(int[] nums, int left, int right){
        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        swap(nums,pivotIndex,left);
        int pivot = nums[left];
        int i = left + 1;
        int j = right;
        while(true){
            // 当i指针还小于等于最右侧 并且i指针的元素小于标杆 那么他就应该在左侧 所以i++
            while (i<=right && nums[i] < pivot){
                i++;
            }
            // 当j指针还大于left(不能是大于等于，因为left上放着的是标杆) 并且j指针大于标杆 那么他就应该在右侧 所以j--
            while (j>left && nums[j] > pivot){
                j--;
            }
            // 左指针大于等于右指针结束循环
            if (i >= j){
                break;
            }

            swap(nums,i++,j--);
        }

        swap(nums,left,j);
        return j;
    }


    public void swap(int[] nums, int i, int j){
        if(i == j){
            return;
        }
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }


    public static void main(String[] args) {
        _912_排序数组_Quick quick = new _912_排序数组_Quick();
        int[] nums = {7,9,4,1,5,3};
//        int[] nums = {9,7,5};
        quick.sortArray(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
